package com.shuyun.xxx.guava.offer;

/**
 * Created by goodb on 2017/5/22.
 * 判断是否是平衡二叉树
 */
public class BalanceTree {
    static class Node{
        private int data;
        private Node left;
        private Node right;
        public Node(int data){
            this.data =data;
        }
    }
    public boolean isBalance(Node head){
        boolean res = true;
        getHeight(head, 1, res);
        return res;
    }

    public int getHeight(Node head, int level, boolean res) {
        if (head == null) {
            return level;
        }
        int lH = getHeight(head.left, level + 1, res);
        if(!res){
            return level;
        }
        int rH = getHeight(head.right, level + 1, res);
        if(!res){
            return level;
        }
        if(Math.abs(lH - rH) > 1){
            res = false;
        }
        return Math.max(lH, rH);
    }

}
